package com.xiaoping.base;

/**
 * 二分查找法
 */
public class BinarySearch {

    private BinarySearch(){}

    private static int find(Comparable [] arr, int l, int r, Comparable target) {
        int mid = l + (r - l)/2;
        if( arr[mid].compareTo(target) == 0 )
            return mid;
        else if( arr[mid].compareTo(target) > 0 )
            return find(arr, l, mid-1, target);
        else
            return find(arr, mid+1, r, target);
    }

    public static int find(Comparable [] arr, Comparable target) {
        return find(arr, 0, arr.length, target);
    }

    public static void main(String[] args) {
        int N = 1000000;
        Integer[] arr = new Integer[N];
        for(int i = 0 ; i < N ; i ++)
            arr[i] = new Integer(i);
        System.out.println(BinarySearch.find(arr, 55555));
    }
}
